To systematically study the implications of additional information aboutroutes provided to certain users (e.g., via GPS-based route guidance systems),we introduce a new class of congestion games in which users have differinginformation sets about the available edges and can only use routes consistingof edges in their information set. After defining the notion of InformationConstrained Wardrop Equilibrium (ICWE) for this class of congestion games andstudying its basic properties, we turn to our main focus: whether additionalinformation can be harmful (in the sense of generating greater equilibriumcosts/delays). We formulate this question in the form of Informational Braes'Paradox (IBP), which extends the classic Braess' Paradox in traffic equilibria,and asks whether users receiving additional information can become worse off.We provide a comprehensive answer to this question showing that in any networkin the series of linearly independent (SLI) class, which is a strict subset ofseries-parallel networks, IBP cannot occur, and in any network that is not inthe SLI class, there exists a configuration of edge-specific cost functions forwhich IBP will occur. In the process, we establish several properties of theSLI class of networks, which include the characterization of the complement ofthe SLI class in terms of embedding a specific set of networks, and also analgorithm which determines whether a graph is SLI in linear time. We furtherprove that the worst-case inefficiency performance of ICWE is no worse than thestandard Wardrop equilibrium.
展开▼
